/*
    SUSAN® - Sole of Unix Save ANything

   Copyright (C) 2002-2010 Hechzh Property
   Copyright (C) 2016-2020 Hechzh Property

   
*/
/*
 * Kern Sibbald, June MMII
 */

/**
 * @file
 * Match Bootstrap Records (used for restores) against
 * Volume Records
 */

/*
 * ***FIXME***
 * Also for efficiency, once a bsr is done, it really should be
 *   delinked from the bsr chain.  This will avoid the above
 *   problem and make traversal of the bsr chain more efficient.
 *
 *   To be done ...
 */

#include "include/susan.h"
#include "stored/bsr.h"
#include "stored/device_control_record.h"
#include "stored/jcr_private.h"
#include "stored/stored.h"
#include "include/jcr.h"

namespace storagedaemon {

const int dbglevel = 500;

/* Forward references */
static int MatchVolume(BootStrapRecord* bsr,
                       BsrVolume* volume,
                       Volume_Label* volrec,
                       bool done);
static int MatchSesstime(BootStrapRecord* bsr,
                         BsrSessionTime* sesstime,
                         DeviceRecord* rec,
                         bool done);
static int MatchSessid(BootStrapRecord* bsr,
                       BsrSessionId* sessid,
                       DeviceRecord* rec);
static int MatchClient(BootStrapRecord* bsr,
                       BsrClient* client,
                       Session_Label* sessrec,
                       bool done);
static int MatchJob(BootStrapRecord* bsr,
                    BsrJob* job,
                    Session_Label* sessrec,
                    bool done);
static int MatchJobType(BootStrapRecord* bsr,
                        BsrJobType* job_type,
                        Session_Label* sessrec,
                        bool done);
static int MatchJobLevel(BootStrapRecord* bsr,
                         BsrJoblevel* job_level,
                         Session_Label* sessrec,
                         bool done);
static int MatchJobid(BootStrapRecord* bsr,
                      BsrJobid* jobid,
                      Session_Label* sessrec,
                      bool done);
static int MatchFindex(BootStrapRecord* bsr,
                       BsrFileIndex* findex,
                       DeviceRecord* rec,
                       bool done);
static int MatchVolfile(BootStrapRecord* bsr,
                        BsrVolumeFile* volfile,
                        DeviceRecord* rec,
                        bool done);
static int MatchVoladdr(BootStrapRecord* bsr,
                        BsrVolumeAddress* voladdr,
                        DeviceRecord* rec,
                        bool done);
static int MatchStream(BootStrapRecord* bsr,
                       BsrStream* stream,
                       DeviceRecord* rec,
                       bool done);
static int MatchAll(BootStrapRecord* bsr,
                    DeviceRecord* rec,
                    Volume_Label* volrec,
                    Session_Label* sessrec,
                    bool done,
                    JobControlRecord* jcr);
static int MatchBlockSesstime(BootStrapRecord* bsr,
                              BsrSessionTime* sesstime,
                              DeviceBlock* block);
static int MatchBlockSessid(BootStrapRecord* bsr,
                            BsrSessionId* sessid,
                            DeviceBlock* block);
static BootStrapRecord* find_smallest_volfile(BootStrapRecord* fbsr,
                                              BootStrapRecord* bsr);

/**
 *
 *  If possible, position the archive device (tape) to read the
 *  next block.
 */
void PositionBsrBlock(BootStrapRecord* bsr, DeviceBlock* block)
{
  /* To be implemented */
}

/**
 *
 *  Do fast block rejection based on bootstrap records.
 *    use_fast_rejection will be set if we have VolSessionId and VolSessTime
 *    in each record. When BlockVer is >= 2, we have those in the block header
 *    so can do fast rejection.
 *
 *   returns:  1 if block may contain valid records
 *             0 if block may be skipped (i.e. it contains no records of
 *                  that can match the bsr).
 *
 */
int MatchBsrBlock(BootStrapRecord* bsr, DeviceBlock* block)
{
  if (!bsr || !bsr->use_fast_rejection || (block->BlockVer < 2)) {
    return 1; /* cannot fast reject */
  }

  for (; bsr; bsr = bsr->next) {
    if (!MatchBlockSesstime(bsr, bsr->sesstime, block)) { continue; }
    if (!MatchBlockSessid(bsr, bsr->sessid, block)) { continue; }
    return 1;
  }
  return 0;
}

static int MatchBlockSesstime(BootStrapRecord* bsr,
                              BsrSessionTime* sesstime,
                              DeviceBlock* block)
{
  if (!sesstime) { return 1; /* no specification matches all */ }
  if (sesstime->sesstime == block->VolSessionTime) { return 1; }
  if (sesstime->next) { return MatchBlockSesstime(bsr, sesstime->next, block); }
  return 0;
}

static int MatchBlockSessid(BootStrapRecord* bsr,
                            BsrSessionId* sessid,
                            DeviceBlock* block)
{
  if (!sessid) { return 1; /* no specification matches all */ }
  if (sessid->sessid <= block->VolSessionId &&
      sessid->sessid2 >= block->VolSessionId) {
    return 1;
  }
  if (sessid->next) { return MatchBlockSessid(bsr, sessid->next, block); }
  return 0;
}

static int MatchFileregex(BootStrapRecord* bsr,
                          DeviceRecord* rec,
                          JobControlRecord* jcr)
{
  if (bsr->fileregex_re == NULL) return 1;

  if (bsr->attr == NULL) { bsr->attr = new_attr(jcr); }

  /*
   * The code breaks if the first record associated with a file is
   * not of this type
   */
  if (rec->maskedStream == STREAM_UNIX_ATTRIBUTES ||
      rec->maskedStream == STREAM_UNIX_ATTRIBUTES_EX) {
    bsr->skip_file = false;
    if (UnpackAttributesRecord(jcr, rec->Stream, rec->data, rec->data_len,
                               bsr->attr)) {
      if (regexec(bsr->fileregex_re, bsr->attr->fname, 0, NULL, 0) == 0) {
        Dmsg2(dbglevel, "Matched pattern, fname=%s FI=%d\n", bsr->attr->fname,
              rec->FileIndex);
      } else {
        Dmsg2(dbglevel, "Didn't match, skipping fname=%s FI=%d\n",
              bsr->attr->fname, rec->FileIndex);
        bsr->skip_file = true;
      }
    }
  }
  return 1;
}

/**
 *
 *      Match Bootstrap records
 *        returns  1 on match
 *        returns  0 no match and Reposition is set if we should
 *                      Reposition the tape
 *       returns -1 no additional matches possible
 */
int MatchBsr(BootStrapRecord* bsr,
             DeviceRecord* rec,
             Volume_Label* volrec,
             Session_Label* sessrec,
             JobControlRecord* jcr)
{
  int status;

  /*
   * The bsr->Reposition flag is set any time a bsr is done.
   *   In this case, we can probably Reposition the
   *   tape to the next available bsr position.
   */
  if (bsr) {
    bsr->Reposition = false;
    status = MatchAll(bsr, rec, volrec, sessrec, true, jcr);
    /*
     * Note, bsr->Reposition is set by MatchAll when
     *  a bsr is done. We turn it off if a match was
     *  found or if we cannot use positioning
     */
    if (status != 0 || !bsr->use_positioning) { bsr->Reposition = false; }
  } else {
    status = 1; /* no bsr => match all */
  }
  return status;
}

/**
 * Find the next bsr that applies to the current tape.
 *   It is the one with the smallest VolFile position.
 */
BootStrapRecord* find_next_bsr(BootStrapRecord* root_bsr, Device* dev)
{
  BootStrapRecord* bsr;
  BootStrapRecord* found_bsr = NULL;

  /* Do tape/disk seeking only if CAP_POSITIONBLOCKS is on */
  if (!root_bsr) {
    Dmsg0(dbglevel, "NULL root bsr pointer passed to find_next_bsr.\n");
    return NULL;
  }
  if (!root_bsr->use_positioning || !root_bsr->Reposition ||
      !dev->HasCap(CAP_POSITIONBLOCKS)) {
    Dmsg2(dbglevel, "No nxt_bsr use_pos=%d repos=%d\n",
          root_bsr->use_positioning, root_bsr->Reposition);
    return NULL;
  }
  Dmsg2(dbglevel, "use_pos=%d repos=%d\n", root_bsr->use_positioning,
        root_bsr->Reposition);
  root_bsr->mount_next_volume = false;
  /* Walk through all bsrs to find the next one to use => smallest file,block */
  for (bsr = root_bsr; bsr; bsr = bsr->next) {
    if (bsr->done || !MatchVolume(bsr, bsr->volume, &dev->VolHdr, 1)) {
      continue;
    }
    if (found_bsr == NULL) {
      found_bsr = bsr;
    } else {
      found_bsr = find_smallest_volfile(found_bsr, bsr);
    }
  }
  /*
   * If we get to this point and found no bsr, it means
   *  that any additional bsr's must apply to the next
   *  tape, so set a flag.
   */
  if (found_bsr == NULL) { root_bsr->mount_next_volume = true; }
  return found_bsr;
}

/**
 * Get the smallest address from this voladdr part
 * Don't use "done" elements
 */
static bool GetSmallestVoladdr(BsrVolumeAddress* va, uint64_t* ret)
{
  bool ok = false;
  uint64_t min_val = 0;

  for (; va; va = va->next) {
    if (!va->done) {
      if (ok) {
        min_val = MIN(min_val, va->saddr);
      } else {
        min_val = va->saddr;
        ok = true;
      }
    }
  }
  *ret = min_val;
  return ok;
}

/* FIXME
 * This routine needs to be fixed to only look at items that
 *   are not marked as done.  Otherwise, it can find a bsr
 *   that has already been consumed, and this will cause the
 *   bsr to be used, thus we may seek back and re-read the
 *   same records, causing an error.  This deficiency must
 *   be fixed.  For the moment, it has been kludged in
 *   read_record.c to avoid seeking back if find_next_bsr
 *   returns a bsr pointing to a smaller address (file/block).
 *
 */
static BootStrapRecord* find_smallest_volfile(BootStrapRecord* found_bsr,
                                              BootStrapRecord* bsr)
{
  BootStrapRecord* return_bsr = found_bsr;
  BsrVolumeFile* vf;
  BsrVolumeBlock* vb;
  uint32_t found_bsr_sfile, bsr_sfile;
  uint32_t found_bsr_sblock, bsr_sblock;
  uint64_t found_bsr_saddr, bsr_saddr;

  /* if we have VolAddr, use it, else try with File and Block */
  if (GetSmallestVoladdr(found_bsr->voladdr, &found_bsr_saddr)) {
    if (GetSmallestVoladdr(bsr->voladdr, &bsr_saddr)) {
      if (found_bsr_saddr > bsr_saddr) {
        return bsr;
      } else {
        return found_bsr;
      }
    }
  }

  /* Find the smallest file in the found_bsr */
  vf = found_bsr->volfile;
  found_bsr_sfile = vf->sfile;
  while ((vf = vf->next)) {
    if (vf->sfile < found_bsr_sfile) { found_bsr_sfile = vf->sfile; }
  }

  /* Find the smallest file in the bsr */
  vf = bsr->volfile;
  bsr_sfile = vf->sfile;
  while ((vf = vf->next)) {
    if (vf->sfile < bsr_sfile) { bsr_sfile = vf->sfile; }
  }

  /* if the bsr file is less than the found_bsr file, return bsr */
  if (found_bsr_sfile > bsr_sfile) {
    return_bsr = bsr;
  } else if (found_bsr_sfile == bsr_sfile) {
    /* Files are equal */
    /* find smallest block in found_bsr */
    vb = found_bsr->volblock;
    found_bsr_sblock = vb->sblock;
    while ((vb = vb->next)) {
      if (vb->sblock < found_bsr_sblock) { found_bsr_sblock = vb->sblock; }
    }
    /* Find smallest block in bsr */
    vb = bsr->volblock;
    bsr_sblock = vb->sblock;
    while ((vb = vb->next)) {
      if (vb->sblock < bsr_sblock) { bsr_sblock = vb->sblock; }
    }
    /* Compare and return the smallest */
    if (found_bsr_sblock > bsr_sblock) { return_bsr = bsr; }
  }
  return return_bsr;
}

/**
 * Called after the signature record so that
 *   we can see if the current bsr has been
 *   fully processed (i.e. is done).
 *  The bsr argument is not used, but is included
 *    for consistency with the other match calls.
 *
 * Returns: true if we should reposition
 *        : false otherwise.
 */
bool IsThisBsrDone(BootStrapRecord* bsr, DeviceRecord* rec)
{
  BootStrapRecord* rbsr = rec->bsr;
  Dmsg1(dbglevel, "match_set %d\n", rbsr != NULL);
  if (!rbsr) { return false; }
  rec->bsr = NULL;
  rbsr->found++;
  if (rbsr->count && rbsr->found >= rbsr->count) {
    rbsr->done = true;
    rbsr->root->Reposition = true;
    Dmsg2(dbglevel, "is_end_this_bsr set Reposition=1 count=%d found=%d\n",
          rbsr->count, rbsr->found);
    return true;
  }
  Dmsg2(dbglevel, "is_end_this_bsr not done count=%d found=%d\n", rbsr->count,
        rbsr->found);
  return false;
}

/**
 * Match all the components of current record
 *   returns  1 on match
 *   returns  0 no match
 *   returns -1 no additional matches possible
 */
static int MatchAll(BootStrapRecord* bsr,
                    DeviceRecord* rec,
                    Volume_Label* volrec,
                    Session_Label* sessrec,
                    bool done,
                    JobControlRecord* jcr)
{
  Dmsg0(dbglevel, "Enter MatchAll\n");
  if (bsr->done) {
    //    Dmsg0(dbglevel, "bsr->done set\n");
    goto no_match;
  }
  if (!MatchVolume(bsr, bsr->volume, volrec, 1)) {
    Dmsg2(dbglevel, "bsr fail bsr_vol=%s != rec read_vol=%s\n",
          bsr->volume->VolumeName, volrec->VolumeName);
    goto no_match;
  }
  Dmsg2(dbglevel, "OK bsr match bsr_vol=%s read_vol=%s\n",
        bsr->volume->VolumeName, volrec->VolumeName);

  if (!MatchVolfile(bsr, bsr->volfile, rec, 1)) {
    if (bsr->volfile) {
      Dmsg3(dbglevel, "Fail on file=%u. bsr=%u,%u\n", rec->File,
            bsr->volfile->sfile, bsr->volfile->efile);
    }
    goto no_match;
  }

  if (!MatchVoladdr(bsr, bsr->voladdr, rec, 1)) {
    if (bsr->voladdr) {
      Dmsg3(dbglevel, "Fail on Addr=%llu. bsr=%llu,%llu\n",
            GetRecordAddress(rec), bsr->voladdr->saddr, bsr->voladdr->eaddr);
    }
    goto no_match;
  }

  if (!MatchSesstime(bsr, bsr->sesstime, rec, 1)) {
    Dmsg2(dbglevel, "Fail on sesstime. bsr=%u rec=%u\n",
          bsr->sesstime->sesstime, rec->VolSessionTime);
    goto no_match;
  }

  /* NOTE!! This test MUST come after the sesstime test */
  if (!MatchSessid(bsr, bsr->sessid, rec)) {
    Dmsg2(dbglevel, "Fail on sessid. bsr=%u rec=%u\n", bsr->sessid->sessid,
          rec->VolSessionId);
    goto no_match;
  }

  /* NOTE!! This test MUST come after sesstime and sessid tests */
  if (!MatchFindex(bsr, bsr->FileIndex, rec, 1)) {
    if (bsr->FileIndex) {
      Dmsg3(dbglevel, "Fail on findex=%d. bsr=%d,%d\n", rec->FileIndex,
            bsr->FileIndex->findex, bsr->FileIndex->findex2);
    } else {
      Dmsg0(dbglevel, "No bsr->FileIndex!\n");
    }
    goto no_match;
  }
  Dmsg3(dbglevel, "match on findex=%d. bsr=%d,%d\n", rec->FileIndex,
        bsr->FileIndex->findex, bsr->FileIndex->findex2);

  if (!MatchFileregex(bsr, rec, jcr)) {
    Dmsg1(dbglevel, "Fail on fileregex='%s'\n", bsr->fileregex);
    goto no_match;
  }

  /* This flag is set by MatchFileregex (and perhaps other tests) */
  if (bsr->skip_file) {
    Dmsg1(dbglevel, "Skipping findex=%d\n", rec->FileIndex);
    goto no_match;
  }

  /*
   * If a count was specified and we have a FileIndex, assume
   *   it is a Susan created bsr (or the equivalent). We
   *   then save the bsr where the match occurred so that
   *   after processing the record or records, we can update
   *   the found count. I.e. rec->bsr points to the bsr that
   *   satisfied the match.
   */
  if (bsr->count && bsr->FileIndex) {
    rec->bsr = bsr;
    Dmsg0(dbglevel, "Leave MatchAll 1\n");
    return 1; /* this is a complete match */
  }

  /*
   * The selections below are not used by Susan's
   *   restore command, and don't work because of
   *   the rec->bsr = bsr optimization above.
   */
  if (!MatchJobid(bsr, bsr->JobId, sessrec, 1)) {
    Dmsg0(dbglevel, "fail on JobId\n");
    goto no_match;
  }
  if (!MatchJob(bsr, bsr->job, sessrec, 1)) {
    Dmsg0(dbglevel, "fail on Job\n");
    goto no_match;
  }
  if (!MatchClient(bsr, bsr->client, sessrec, 1)) {
    Dmsg0(dbglevel, "fail on Client\n");
    goto no_match;
  }
  if (!MatchJobType(bsr, bsr->JobType, sessrec, 1)) {
    Dmsg0(dbglevel, "fail on Job type\n");
    goto no_match;
  }
  if (!MatchJobLevel(bsr, bsr->JobLevel, sessrec, 1)) {
    Dmsg0(dbglevel, "fail on Job level\n");
    goto no_match;
  }
  if (!MatchStream(bsr, bsr->stream, rec, 1)) {
    Dmsg0(dbglevel, "fail on stream\n");
    goto no_match;
  }
  return 1;

no_match:
  if (bsr->next) {
    return MatchAll(bsr->next, rec, volrec, sessrec, bsr->done && done, jcr);
  }
  if (bsr->done && done) {
    Dmsg0(dbglevel, "Leave match all -1\n");
    return -1;
  }
  Dmsg0(dbglevel, "Leave match all 0\n");
  return 0;
}

static int MatchVolume(BootStrapRecord* bsr,
                       BsrVolume* volume,
                       Volume_Label* volrec,
                       bool done)
{
  if (!volume) { return 0; /* Volume must match */ }
  if (bstrcmp(volume->VolumeName, volrec->VolumeName)) {
    Dmsg1(dbglevel, "MatchVolume=%s\n", volrec->VolumeName);
    return 1;
  }
  if (volume->next) { return MatchVolume(bsr, volume->next, volrec, 1); }
  return 0;
}

static int MatchClient(BootStrapRecord* bsr,
                       BsrClient* client,
                       Session_Label* sessrec,
                       bool done)
{
  if (!client) { return 1; /* no specification matches all */ }
  if (bstrcmp(client->ClientName, sessrec->ClientName)) { return 1; }
  if (client->next) { return MatchClient(bsr, client->next, sessrec, 1); }
  return 0;
}

static int MatchJob(BootStrapRecord* bsr,
                    BsrJob* job,
                    Session_Label* sessrec,
                    bool done)
{
  if (!job) { return 1; /* no specification matches all */ }
  if (bstrcmp(job->Job, sessrec->Job)) { return 1; }
  if (job->next) { return MatchJob(bsr, job->next, sessrec, 1); }
  return 0;
}

static int MatchJobType(BootStrapRecord* bsr,
                        BsrJobType* job_type,
                        Session_Label* sessrec,
                        bool done)
{
  if (!job_type) { return 1; /* no specification matches all */ }
  if (job_type->JobType == sessrec->JobType) { return 1; }
  if (job_type->next) { return MatchJobType(bsr, job_type->next, sessrec, 1); }
  return 0;
}

static int MatchJobLevel(BootStrapRecord* bsr,
                         BsrJoblevel* job_level,
                         Session_Label* sessrec,
                         bool done)
{
  if (!job_level) { return 1; /* no specification matches all */ }
  if (job_level->JobLevel == sessrec->JobLevel) { return 1; }
  if (job_level->next) {
    return MatchJobLevel(bsr, job_level->next, sessrec, 1);
  }
  return 0;
}

static int MatchJobid(BootStrapRecord* bsr,
                      BsrJobid* jobid,
                      Session_Label* sessrec,
                      bool done)
{
  if (!jobid) { return 1; /* no specification matches all */ }
  if (jobid->JobId <= sessrec->JobId && jobid->JobId2 >= sessrec->JobId) {
    return 1;
  }
  if (jobid->next) { return MatchJobid(bsr, jobid->next, sessrec, 1); }
  return 0;
}

static int MatchVolfile(BootStrapRecord* bsr,
                        BsrVolumeFile* volfile,
                        DeviceRecord* rec,
                        bool done)
{
  if (!volfile) { return 1; /* no specification matches all */ }
  /**
   * The following code is turned off because this should now work
   *   with disk files too, though since a "volfile" is 4GB, it does
   *   not improve performance much.
   */
  if (volfile->sfile <= rec->File && volfile->efile >= rec->File) { return 1; }
  /* Once we get past last efile, we are done */
  if (rec->File > volfile->efile) { volfile->done = true; /* set local done */ }
  if (volfile->next) {
    return MatchVolfile(bsr, volfile->next, rec, volfile->done && done);
  }

  /* If we are done and all prior matches are done, this bsr is finished */
  if (volfile->done && done) {
    bsr->done = true;
    bsr->root->Reposition = true;
    Dmsg2(dbglevel, "bsr done from volfile rec=%u volefile=%u\n", rec->File,
          volfile->efile);
  }
  return 0;
}

static int MatchVoladdr(BootStrapRecord* bsr,
                        BsrVolumeAddress* voladdr,
                        DeviceRecord* rec,
                        bool done)
{
  if (!voladdr) { return 1; /* no specification matches all */ }

  uint64_t addr = GetRecordAddress(rec);
  Dmsg6(dbglevel,
        "MatchVoladdr: saddr=%llu eaddr=%llu recaddr=%llu sfile=%u efile=%u "
        "recfile=%u\n",
        voladdr->saddr, voladdr->eaddr, addr, voladdr->saddr >> 32,
        voladdr->eaddr >> 32, addr >> 32);

  if (voladdr->saddr <= addr && voladdr->eaddr >= addr) { return 1; }
  /* Once we get past last eblock, we are done */
  if (addr > voladdr->eaddr) { voladdr->done = true; /* set local done */ }
  if (voladdr->next) {
    return MatchVoladdr(bsr, voladdr->next, rec, voladdr->done && done);
  }

  /* If we are done and all prior matches are done, this bsr is finished */
  if (voladdr->done && done) {
    bsr->done = true;
    bsr->root->Reposition = true;
    Dmsg2(dbglevel, "bsr done from voladdr rec=%llu voleaddr=%llu\n", addr,
          voladdr->eaddr);
  }
  return 0;
}


static int MatchStream(BootStrapRecord* bsr,
                       BsrStream* stream,
                       DeviceRecord* rec,
                       bool done)
{
  if (!stream) { return 1; /* no specification matches all */ }
  if (stream->stream == rec->Stream) { return 1; }
  if (stream->next) { return MatchStream(bsr, stream->next, rec, 1); }
  return 0;
}

static int MatchSesstime(BootStrapRecord* bsr,
                         BsrSessionTime* sesstime,
                         DeviceRecord* rec,
                         bool done)
{
  if (!sesstime) { return 1; /* no specification matches all */ }
  if (sesstime->sesstime == rec->VolSessionTime) { return 1; }
  if (rec->VolSessionTime > sesstime->sesstime) { sesstime->done = true; }
  if (sesstime->next) {
    return MatchSesstime(bsr, sesstime->next, rec, sesstime->done && done);
  }
  if (sesstime->done && done) {
    bsr->done = true;
    bsr->root->Reposition = true;
    Dmsg0(dbglevel, "bsr done from sesstime\n");
  }
  return 0;
}

/**
 * Note, we cannot mark bsr done based on session id because we may
 *  have interleaved records, and there may be more of what we want
 *  later.
 */
static int MatchSessid(BootStrapRecord* bsr,
                       BsrSessionId* sessid,
                       DeviceRecord* rec)
{
  if (!sessid) { return 1; /* no specification matches all */ }
  if (sessid->sessid <= rec->VolSessionId &&
      sessid->sessid2 >= rec->VolSessionId) {
    return 1;
  }
  if (sessid->next) { return MatchSessid(bsr, sessid->next, rec); }
  return 0;
}

/**
 * When reading the Volume, the Volume Findex (rec->FileIndex) always
 *   are found in sequential order. Thus we can make optimizations.
 *
 *  ***FIXME*** optimizations
 * We could optimize by removing the recursion.
 */
static int MatchFindex(BootStrapRecord* bsr,
                       BsrFileIndex* findex,
                       DeviceRecord* rec,
                       bool done)
{
  if (!findex) { return 1; /* no specification matches all */ }
  if (!findex->done) {
    if (findex->findex <= rec->FileIndex && findex->findex2 >= rec->FileIndex) {
      Dmsg3(dbglevel, "Match on findex=%d. bsrFIs=%d,%d\n", rec->FileIndex,
            findex->findex, findex->findex2);
      return 1;
    }
    if (rec->FileIndex > findex->findex2) { findex->done = true; }
  }
  if (findex->next) {
    return MatchFindex(bsr, findex->next, rec, findex->done && done);
  }
  if (findex->done && done) {
    bsr->done = true;
    bsr->root->Reposition = true;
    Dmsg1(dbglevel, "bsr done from findex %d\n", rec->FileIndex);
  }
  return 0;
}

uint64_t GetBsrStartAddr(BootStrapRecord* bsr, uint32_t* file, uint32_t* block)
{
  uint64_t bsr_addr = 0;
  uint32_t sfile = 0, sblock = 0;

  if (bsr) {
    if (bsr->voladdr) {
      bsr_addr = bsr->voladdr->saddr;
      sfile = bsr_addr >> 32;
      sblock = (uint32_t)bsr_addr;

    } else if (bsr->volfile && bsr->volblock) {
      bsr_addr =
          (((uint64_t)bsr->volfile->sfile) << 32) | bsr->volblock->sblock;
      sfile = bsr->volfile->sfile;
      sblock = bsr->volblock->sblock;
    }
  }

  if (file && block) {
    *file = sfile;
    *block = sblock;
  }

  return bsr_addr;
}

/* ****************************************************************
 * Routines for handling volumes
 */
static VolumeList* new_restore_volume()
{
  VolumeList* vol;
  vol = (VolumeList*)malloc(sizeof(VolumeList));
  memset(vol, 0, sizeof(VolumeList));
  return vol;
}

/**
 * Add current volume to end of list, only if the Volume
 * is not already in the list.
 *
 *   returns: 1 if volume added
 *            0 if volume already in list
 */
static bool AddRestoreVolume(JobControlRecord* jcr, VolumeList* vol)
{
  VolumeList* next = jcr->impl->VolList;

  /* Add volume to volume manager's read list */
  AddReadVolume(jcr, vol->VolumeName);

  if (!next) {                /* list empty ? */
    jcr->impl->VolList = vol; /* yes, add volume */
  } else {
    /* Loop through all but last */
    for (; next->next; next = next->next) {
      if (bstrcmp(vol->VolumeName, next->VolumeName)) {
        /* Save smallest start file */
        if (vol->start_file < next->start_file) {
          next->start_file = vol->start_file;
        }
        return false; /* already in list */
      }
    }
    /* Check last volume in list */
    if (bstrcmp(vol->VolumeName, next->VolumeName)) {
      if (vol->start_file < next->start_file) {
        next->start_file = vol->start_file;
      }
      return false; /* already in list */
    }
    next->next = vol; /* add volume */
  }
  return true;
}

/**
 * Create a list of Volumes (and Slots and Start positions) to be
 *  used in the current restore job.
 */
void CreateRestoreVolumeList(JobControlRecord* jcr)
{
  char *p, *n;
  VolumeList* vol;

  /*
   * Build a list of volumes to be processed
   */
  jcr->impl->NumReadVolumes = 0;
  jcr->impl->CurReadVolume = 0;
  if (jcr->impl->read_session.bsr) {
    BootStrapRecord* bsr = jcr->impl->read_session.bsr;
    if (!bsr->volume || !bsr->volume->VolumeName[0]) { return; }
    for (; bsr; bsr = bsr->next) {
      BsrVolume* bsrvol;
      BsrVolumeFile* volfile;
      uint32_t sfile = UINT32_MAX;

      /* Find minimum start file so that we can forward space to it */
      for (volfile = bsr->volfile; volfile; volfile = volfile->next) {
        if (volfile->sfile < sfile) { sfile = volfile->sfile; }
      }
      /* Now add volumes for this bsr */
      for (bsrvol = bsr->volume; bsrvol; bsrvol = bsrvol->next) {
        vol = new_restore_volume();
        bstrncpy(vol->VolumeName, bsrvol->VolumeName, sizeof(vol->VolumeName));
        bstrncpy(vol->MediaType, bsrvol->MediaType, sizeof(vol->MediaType));
        bstrncpy(vol->device, bsrvol->device, sizeof(vol->device));
        vol->Slot = bsrvol->Slot;
        vol->start_file = sfile;
        if (AddRestoreVolume(jcr, vol)) {
          jcr->impl->NumReadVolumes++;
          Dmsg2(400, "Added volume=%s mediatype=%s\n", vol->VolumeName,
                vol->MediaType);
        } else {
          Dmsg1(400, "Duplicate volume %s\n", vol->VolumeName);
          free((char*)vol);
        }
        sfile = 0; /* start at beginning of second volume */
      }
    }
  } else {
    /* This is the old way -- deprecated */
    for (p = jcr->impl->dcr->VolumeName; p && *p;) {
      n = strchr(p, '|'); /* volume name separator */
      if (n) { *n++ = 0; /* Terminate name */ }
      vol = new_restore_volume();
      bstrncpy(vol->VolumeName, p, sizeof(vol->VolumeName));
      bstrncpy(vol->MediaType, jcr->impl->dcr->media_type,
               sizeof(vol->MediaType));
      if (AddRestoreVolume(jcr, vol)) {
        jcr->impl->NumReadVolumes++;
      } else {
        free((char*)vol);
      }
      p = n;
    }
  }
}

void FreeRestoreVolumeList(JobControlRecord* jcr)
{
  VolumeList* vol = jcr->impl->VolList;
  VolumeList* tmp;

  for (; vol;) {
    tmp = vol->next;
    RemoveReadVolume(jcr, vol->VolumeName);
    free(vol);
    vol = tmp;
  }
  jcr->impl->VolList = NULL;
}

} /* namespace storagedaemon */
